package 剑指专题.二叉树;


/*
 * Author：江松
 * Date：2023/3/24 11:51
 *
 根据--先序中序,构建二叉树
 */

import org.omg.CORBA.INTERNAL;

import java.util.HashMap;

public class Main4 {
    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
        public TreeNode(int val) {
            this.val = val;
        }
    }

    //映射前序遍历的点，在中序遍历中的位置
    HashMap<Integer, Integer>map=new HashMap<>();
    int []pre,vin;
    public TreeNode create(int prel,int prer,int midl,int midr){
        if(prel>prer)return null;
        int val=pre[prel];
        int index_root=map.get(val);
        int ltree=index_root-midl;
        System.out.println("i:"+index_root+",val"+val);
        TreeNode root=new TreeNode(val);
        root.left=create(prel+1,prel+ltree,midl,index_root);
        root.right=create(prel+ltree+1,prer,index_root+1,midr);
        return root;
    }

    public TreeNode reConstructBinaryTree(int [] pre,int [] vin) {
        for(int i=0;i<vin.length;++i){
            map.put(vin[i],i);
        }
        this.vin=vin;
        this.pre=pre;
        return create(0,pre.length-1,0,vin.length-1);
    }
}
